package q295_MedianFinder;

import java.util.PriorityQueue;

/*
考虑使用两个队列来实现在数据流中找出中位数：
首先queMin是按照从大到小排序的队列 例如输入 1 2 3 则队列排序为 3 2 1 使用peek输出3 poll也是弹出队头3
queMax则相反 因此我们向数据结构输入 1 2 3 4 5 6 就会变成 min ： 3 2 1 max ： 4 5 6
因此 两者的队头平均即为中位数 当首次加入 或者 num小于min的队头时 num会优先加入min 因此min的队头能够保持为中位数
如果发现min的数量超过了max两个 则代表min的队头不再是中位数 应该将其队头放入max中
同样的如果我们发现输入的num大于当前的queMin的队头 那么应该放入max 代表其是一个大于中位数的数
而当max大于min时 应该将max队头放入min中
即可完成该数据结构
 */
public class MedianFinder {
    PriorityQueue<Integer> queMin;
    PriorityQueue<Integer> queMax;
    public MedianFinder() {
        queMin = new PriorityQueue<>((a, b) -> (b - a));
        queMax = new PriorityQueue<>((a, b) -> (a - b));
    }
    public void addNum(int num) {
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            if (queMax.size() + 1 < queMin.size()) queMax.offer(queMin.poll());
        } else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) queMin.offer(queMax.poll());
        }
    }

    public double findMedian() {
        if (queMin.size() > queMax.size()) return queMin.peek();
        return ((double)queMax.peek() + (double)queMin.peek()) / 2;
    }
}
